package leetcode_jz_offer.day10_dp;

/**
 * 请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
 **/
/**
 * 无重复字符的最长子串
 * 字符存储到set集合，如果有重复的直接之前的从set集合移除，加进来新的字符
 */

import java.util.HashSet;
import java.util.Set;

/**
 * 思路：滑动窗口
 * 以(a)bcabcbb 开始的最长字符串为 (abc)abcbb；
 * 以a(b)cabcbb 开始的最长字符串为 a(bca)bcbb；
 * 以ab(c)abcbb 开始的最长字符串为 ab(cab)cbb；
 * 以abc(a)bcbb 开始的最长字符串为 abc(abc)bb；
 * 以abca(b)cbb 开始的最长字符串为 abca(bc)bb；
 * 以abcab(c)bb 开始的最长字符串为 abcab(cb)b；
 * 以abcabc(b)b 开始的最长字符串为 abcabc(b)b；
 * 以abcabcb(b) 开始的最长字符串为 abcabcb(b).
 * 此时观察，我们需要边加入字符边移除字符。将字符逐个存入set集合，如果后面的元素有重复出现的字符，则set集合元素出集合直到无此重复元素，再将此元素入set集合
 */
public class Num48_无重复字符的最长子串 {
    public int lengthOfLongestSubstring(String s) {
        int max=0;
        int right=0;
        Set<Character> set = new HashSet<>();
        for (int left = 0; left < s.length(); left++) {
            //左指针向后遍历，移除left的前一个元素
            if(left!=0){
                set.remove(s.charAt(left-1));
            }
            //左指针定住，右指针向后走，元素不但放入set集合，直到遇到与set中元素重复或走到空记录长度
            while (right<s.length()&&(!set.contains(s.charAt(right)))){
                set.add(s.charAt(right));
                right++;
            }
            max=Math.max(max,right-left);
        }
        return max;
    }
}
